package com.xinwei.leetcode.数组;

import java.util.HashMap;
import java.util.HashSet;

// https://leetcode-cn.com/problems/contains-duplicate-ii/
public class _219_存在重复元素II {
    // 暴力破解 -->超出时间限制
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j] == nums[i] && j - i <= k) {
                    return true;
                }
            }
        }
        return false;
    }

    // 哈希表
    public static boolean containsNearbyDuplicate1(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                if (i - hashMap.get(nums[i]) <= k) {
                    return true;
                }
            }
            hashMap.put(nums[i], i);
        }
        return false;
    }

    // 方法二  二叉搜索树

    // 方法三 （散列表） --> 时间复杂度：O(n)   空间复杂度：O(min(n, k))
    // 制造一个大小为k的滑动窗口
//    遍历数组，对于每个元素做以下操作：
//    在散列表中搜索当前元素，如果找到了就返回 true。
//    在散列表中插入当前元素。
//    如果当前散列表的大小超过了k， 删除散列表中最旧的元素。
    public static boolean containsNearbyDuplicate2(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }


}
